package basic.study.leetcode;

/**
 * @ClassName Mid34
 * @Description 在排序数组中查找元素的第一个和最后一个位置
 * @Company inspur
 * @Author Kevin
 * @Date 2020/6/19 11:18
 * @Version 1.0
 */
public class Mid34 {
    public int[] searchRange(int[] nums, int target) {
        int[] result = new int[2];
        result[0] = findFirstPlace(nums, target);
        result[1] = findLastPlace(nums, target);
        return result;

    }

    public int findFirstPlace(int[] nums, int target) {
        int start = 0;
        int end = nums.length - 1;
        int mid;
        while (start <= end) {
            mid = start + ((end - start)>>1);
            if (nums[mid] > target) {
                end = mid - 1;
            } else if (nums[mid] < target) {
                start = mid + 1;
            } else {
                if (mid == 0 || nums[mid -1] != nums[mid]) return mid;
                else end = mid -1;
            }
        }
        return -1;
    }

    public int findLastPlace(int[] nums, int target) {
        int start = 0;
        int end = nums.length - 1;
        int mid;
        while (start <= end) {
            mid = start + ((end - start)>>1);
            if (nums[mid] > target) {
                end = mid - 1;
            } else if (nums[mid] < target) {
                start = mid + 1;
            } else {
                if (mid == nums.length-1 || nums[mid+1] != nums[mid]) return mid;
                else start = mid + 1;
            }
        }
        return -1;
    }
}
